package com.itzmn.datastructure.sort;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/9 14:30
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 堆排序
 *
 *  思路：
 *  首先需要建堆，然后进行排序
 *  将数组递增显示
 *
 *  首先将数组建堆，建大顶堆，完成之后将第一位也即是最大数与最后一位交换，然后将除去最后一位的数组再次建立大顶堆
 *  ，，然后循环
 *
 *
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] ints = {5,2,4,6,3,7,1};
        new HeapSort().heapSort(ints);
    }

    /**
     * 开始堆排序
     * @param arrs
     */
    public void heapSort(int arrs[]){

        for (int i=0;i<arrs.length;i++){

            maxHeap(arrs,arrs.length-i);
            int tem = arrs[0];
            arrs[0] = arrs[arrs.length-1-i];
            arrs[arrs.length-1-i] = tem;
        }

        log(arrs);
    }

    /**
     * 构建大顶堆
     * @param arrs
     */
    public void maxHeap(int arrs[],int size){
        for (int i=arrs.length-1;i>=0;i--){
            initHeap(arrs,i,size);
        }
    }

    /**
     * 构建堆，如果父节点比子节点小，需要重新构建
     * @param arrs
     * @param currentNodeIndex
     * @param size
     */
    public void initHeap(int arrs[],int currentNodeIndex,int size){

        if (currentNodeIndex>=size){
            return;
        }

        int leftIndex = 2*currentNodeIndex+1;
        int rightIndex = 2*currentNodeIndex+2;

        //假设最大的节点就是现在这个节点
        int max = currentNodeIndex;

        //判断坐标是否出界，也即是他有没有左子节点
        if (leftIndex<size){
            //如果左边的节点大，记录坐标
            if (arrs[max]<arrs[leftIndex]){
                max = leftIndex;
            }
        }
        if (rightIndex<size){
            if (arrs[max]<arrs[rightIndex]){
                max = rightIndex;
            }
        }

        //说明当前堆不是正确的，需要重新构建
        if (max != currentNodeIndex){
            int tem = arrs[currentNodeIndex];
            arrs[currentNodeIndex] = arrs[max];
            arrs[max]=tem;

            initHeap(arrs,max,size);
        }



    }
    public void log(int arrs[]){

        for (int i=0;i<arrs.length;i++){
            System.out.print(arrs[i]+" ");
        }
        System.out.println();
    }
}
